package problem126_Word_Ladder_II;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Solution {
	private Map<String,List<String>> map=new HashMap<>();
	List<List<String>> result=new LinkedList<>();
	
	public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
		Set<String> unVisted=new HashSet<>(wordList);
		Queue<String> queue=new LinkedList<>();
		queue.add(beginWord);
		unVisted.add(endWord);
		Set<String> currentLevelVisted=new HashSet<>();
		boolean found=false;
		while(!queue.isEmpty()){
			int numPerLevel=queue.size();
			while(numPerLevel-->0){
				String top=queue.poll();
				StringBuilder current=new StringBuilder(top);
				for(int i=0;i<current.length();i++){
					char tmp=current.charAt(i);
					for(char c='a';c<='z';c++){
						if(current.charAt(i)==c)	continue;
						current.setCharAt(i, c);
						String newWord=current.toString();
						found=newWord.equals(endWord);
						if(unVisted.contains(newWord)){
							if(currentLevelVisted.add(newWord)){
								queue.add(newWord);
							}
							if(map.get(newWord)==null){
								map.put(newWord, new LinkedList<>());
							}
							map.get(newWord).add(top);
						}
					}
					current.setCharAt(i, tmp);
				}
			}
			unVisted.removeAll(currentLevelVisted);
			currentLevelVisted.clear();
			if(found)
				break;
		}
		System.out.println(map);
		backTrace(endWord,beginWord,new LinkedList<>());
		return result;
	}
	
	private void backTrace(String end,String begin,List<String> list){
		list.add(0,end);
		if(end.equals(begin)){
			result.add(new ArrayList<>(list));
			return;
		}
		if(map.get(end)!=null){
			for(String s:map.get(end)){
				backTrace(s,begin,list);
				list.remove(0);
			}
		}
	}
	
	public static void main(String[] args){
		List<String> words=Arrays.asList(new String[]{"hot","dot","dog","lot","log"});
		System.out.println(new Solution().findLadders("hit", "cog", words));
	}
}
